备用返回通道

转到题目

题目描述

对于给定的 n 行 m 列的矩阵，每一个元素要么是 '0'，要么是 '1'。每一轮，你可以进行一次以下操作：

• 选择一行的元素，将其全部反置，即 '0' 变为 '1'，'1' 变为 '0'。

请你帮助小歪判断，若能进行任意多轮操作（也可以不进行操作），至多能使得多少列的元素均为 '1'。你只需要输出这个最大值。

输入描述

• 第一行输入两个正整数 n, m (1 ≤ n, m ≤ 3 × 10^3)，分别表示矩阵的行数和列数。
• 此后 n 行，每行输入一个长度为 m、仅由 '0' 和 '1' 构成的字符串，代表矩阵每一行中的元素。

输出描述

输出一个整数，表示至多能使得多少列的元素均为 '1'。

示例1

输入

3 4
1111
1111
1111

输出

4

说明

在这个样例中，不需要进行操作，所有列的元素均为 '1'。

示例2

输入

3 2
01
10
11

输出

1

说明

在这个样例中，我们可以选择对第一行进行操作，使得第一行变为 '10'，此时，第一列的元素均为 '1'。

题目思路

• 观察发现:
  • 每次行的翻转，都会改变每一列n个元素的状态
• 想要尽可能多的列可以都为1:
  • 至少要保证，尽可能多的列，在每一行上的变化趋势相同,是同步的
    • 否则没办法转移到行为1
• 怎么去寻找这样的列呢?
  • 不难发现，对列上的字符串进行计数,这样。
  • 具有相同趋势的列会被计数在一种类型上。
• 这样，去寻找最多的计数，就是答案。